package com.lanqiaofinal11;

/**
 * @author `RKC`
 * @date 2022/6/17 10:54
 */
public class E玩具蛇 {

    private static final int N = 5;
    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private static boolean[][] g = new boolean[N][N];
    private static int ans = 0;

    public static void main(String[] args) {
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                g[i][j] = true;
                dfs(i, j, 1);
                g[i][j] = false;
            }
        }
        System.out.println(ans);
    }

    private static void dfs(int x, int y, int k) {
        if (k == 16) {
            ans++;
            return;
        }
        for (int[] dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx < 1 || nx > 4 || ny < 1 || ny > 4 || g[nx][ny]) continue;
            g[nx][ny] = true;
            dfs(nx, ny, k + 1);
            g[nx][ny] = false;
        }
    }
}
